繼第 9 天的「48. Rotate Image」，今天來解 73 這題！還沒看過第 9 天或再之前天數的朋友，歡迎也去看看~

話不多說，我們開始吧！

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/set-matrix-zeroes

演算法與資料結構

• Matrix

題意

給予一個大小 m x n 的二維矩陣，當某個位置的元素為 0 時，所處的欄和列的所有元素都要設定為 0 。

條件

• In place

Follow up

• 直接了當的解法會用到 O(mn) 的空間，但是這樣不好，安堆。
• 優化之後會用到 O(m + n) 的空間，但是這不是最佳解。
• 可以達到只用 O(1)

解說

• 列 - row
• 欄 - column

Hash Map?

看了以前自己的筆記，當時一開始的解就用了兩個 Sets 來看哪些欄和列需要變換成 0 。就是 Follow up 裡的 O(m + n)

優化

根據題目得知只要有 0 的位置，整列和整欄就必須換成 0

既然都要變成 0 了，那我們就可以把

• 第 0 欄
• 第 0 列

作為 Hash Map 等同用途之用。

步驟

• 走訪過二維陣列，標記需要變成 0 的欄和列
• 根據第 0 欄和第 0 列的標記變換二維陣列的元素

例外 - 第 0 欄和第 0 列

當第 0 欄和第 0 列有遇到 0 時，就必須要另外標記需要變更。

• 第 0 列：可以透過完整走訪觀察
  • 當變更完非 0 的元素，可以透過 [0][0] 判斷是否需要把第 0 列全部換成 0
• 第 0 欄：
  • 第 0 欄身兼標記的功能 [0][0] 被拿去當第 0 列用的標記
  • 因此需要一個變數標記需不需要變成 0

程式碼

說明和各區間的時間複雜度接註解在行內。

class Solution {
    func setZeroes(_ matrix: inout [[Int]]) {
        var shouldFirstColumnBecomeZero = false
        
        // 1. 開始標記需要變成 0 的欄和列
        //
        // 時間複雜度: O(m)
        for row in 0..<matrix.count {
            // 當地 0 欄有出現 0
            // 就標記需要變更
            if matrix[row][0] == 0 {
                shouldFirstColumnBecomeZero = true
            }
            
            // 第 0 欄已經在 `if matrix[row][0] == 0 {`
            // 被檢查過了，因此欄的走訪從 1 開始
            //
            // 時間複雜度: O(n)
            for column in 1..<matrix[0].count {
                if matrix[row][column] == 0 {
                    matrix[row][0] = 0
                    matrix[0][column] = 0
                }
            }
        }
        
        // 2. 根據第 0 欄和第 0 列改 0
        // 時間複雜度: O(m)
        for row in 1..<matrix.count {
            // 時間複雜度: O(n)
            for column in 1..<matrix[0].count {
                if matrix[row][0] == 0 || matrix[0][column] == 0 {
                    matrix[row][column] = 0
                }
            }
        }
        
        // 3. 第 0 列的處理
        // 時間複雜度: O(m)
        if matrix[0][0] == 0 {
            for column in 1..<matrix[0].count {
                matrix[0][column] = 0
            }
        }
        
        // 4. 第 0 欄的處理
        // 時間複雜度: O(n)
        if shouldFirstColumnBecomeZero {
            for row in 0..<matrix.count {
                matrix[row][0] = 0
            }
        }
    }
}

執行結果

• Runtime: 81ms (Beats 96.55%)
• Memory: 14.3MB (Beats 78.33%)

複雜度分析

二維陣列或矩陣的大小為 m x n

時間複雜度

• 完整走訪矩陣兩次: O(2mn)
• 走訪行和列各一次: O(m + n)

合併後為

O(2mn + m + n)

因為 Big O 只考慮最高項，因此簡化為：

O(mn)

結語

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！